// 给你链表的头节点head，再给一个正整数k，k的值小于或等于链表的长度
// 每k个节点一组进行翻转，并返回修改后的链表，如果链表节点总数不是k的整数倍，则将最后剩余的节点保持原有顺序

// 思路：需要计算index达到k的倍数时，记录需要反转区间的前一个节点pre，反转后，更新新一轮的pre
// 时间复杂度：O(n)
// 空间复杂度：O(1)

const { LinkedList, ListNode} = require('./64.设计链表')

function reverseKGroup(head, k) {
    let dummyHead = new ListNode(0, head)
    let index = 0
    let pre = dummyHead
    let tail = dummyHead.next
    while (tail) {
        index++
        if (index % k === 0) {
            pre = reverse(pre, tail.next)
            tail = pre.next
        } else {
            tail = tail.next
        }
    }
    return dummyHead.next
}

function reverse(preNode, tailNext) {
    let pre = preNode
    let firstNode = preNode.next
    let cur = preNode.next
    let temp
    while (cur !== tailNext) {
        temp = cur.next
        cur.next = pre
        pre =cur
        cur = temp
    }
    // 最后一个元素移到最前面，第一个元素移到了最后面，更新preNode和firstNode的指向
    preNode.next = pre
    firstNode.next = tailNext
    return firstNode
}

let head = [1, 2, 3, 4, 5,6,7], k = 3
let node = new LinkedList(head)
let res = reverseKGroup(node.head, k)
console.log(res);